/**
 *给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
 *
 * 返回执行此操作后，grid 中最大的岛屿面积是多少？
 *
 * 岛屿 由一组上、下、左、右四个方向相连的 1 形成。
 * https://leetcode.cn/problems/making-a-large-island/description/j
 */
class LargestIsland {
    int[] dir = new int[] {0, -1, 0, 1, 0};
    int row, col;

    public int largestIsland(int[][] grid) {
        // 可以将 一格水 变成 陆地
        // 陆地为 1，水为 0
        // 为每一个岛屿编号，并记录面积
        row = grid.length;
        col = grid[0].length;
        HashMap<Integer, Integer> islands = new HashMap<>();
        List<int[]> spaces = new ArrayList<>(); // 记录 水域

        int mark = 2; // 岛屿的编号，从 2 开始
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                // 如果是陆地
                if (grid[i][j] == 1) {
                    int area = expand(grid, i, j, mark); // 这个岛屿的面积
                    islands.put(mark ++, area); // 岛屿编号 -- 岛屿面积
                } else if (grid[i][j] == 0) {  // 如果是 河流
                    spaces.add(new int[] {i, j});
                }
            }
        }
        if (spaces.size() == 0) {
            return row * col;
        } 

        int src = 1; // 记录最终的计算面积
        // 开始判断 所有连接起来的情况

        for (int[] space : spaces) {
            int x = space[0], y = space[1];
            HashSet<Integer> link = new HashSet<>();
            // 四个方向
            int cur = 1; // 至少面积为 1
            for (int i = 0; i < 4; i ++) {
                int nx = dir[i] + x;
                int ny = dir[i + 1] + y;

                if (nx < 0 || nx >= row || ny < 0 || ny >= col || grid[nx][ny] == 0) {
                    continue;
                }
                link.add(grid[nx][ny]);
            }
            for (Integer k : link) {
                cur += islands.get(k);
            }
            src = Math.max(src, cur);
        }

        return src;
    }

    private int expand(int[][] grid, int x, int y, int mark) {
        grid[x][y] = mark;

        int ret = 1; // 记录当前岛屿的总面积
        for (int i = 0; i < 4; i ++) {
            int nx = dir[i] + x;
            int ny = dir[i + 1] + y;

            if (nx < 0 || nx >= row || ny < 0 || ny >= col || grid[nx][ny] == mark || grid[nx][ny] == 0) {
                continue;
            }

            ret += expand(grid, nx, ny, mark);
        }
        return ret;
    }
}